<!doctype html>
<html lang="en" ontouchmove>
<head>
    <title>Hands-on: X25519 Key Exchange</title>
    <meta charset="utf-8"/>
    <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no"/>
    <meta name="format-detection" content="telephone=no"/>
    <meta name="title" content="Hands-on: X25519 Key Exchange"/>
    <meta name="description" content="An explanation and demonstration of Curve25519 Key Exchange"/>
    <link rel="stylesheet" href="frombootstrap.css?bustin=1655425219"/>
    <link rel="stylesheet" href="x25519.css?bustin=1655425219"/>
    <script type="module" async src="site.js?bustin=1655425219"></script>

    <!-- Facebook Meta Tags -->
    <meta property="og:url" content="https://x25519.xargs.org/">
    <meta property="og:type" content="website">
    <meta property="og:title" content="Hands-on: X25519 Key Exchange">
    <meta property="og:description"
          content="An explanation and demonstration of the key exchange used by TLS and QUIC.">
    <meta property="og:image" content="https://x25519.xargs.org/images/og.png">

    <!-- Twitter Meta Tags -->
    <meta name="twitter:card" content="summary_large_image">
    <meta property="twitter:domain" content="x25519.xargs.org">
    <meta property="twitter:url" content="https://x25519.xargs.org/">
    <meta name="twitter:title" content="Hands-on: X25519 Key Exchange">
    <meta name="twitter:description"
          content="An explanation and demonstration of the key exchange used by TLS and QUIC.">
    <meta name="twitter:image" content="https://x25519.xargs.org/images/og.png">

    <!-- favicons -->
    <link rel="apple-touch-icon" sizes="152x152" href="favicon/apple-touch-icon.png">
    <link rel="icon" type="image/png" sizes="32x32" href="favicon/favicon-32x32.png">
    <link rel="icon" type="image/png" sizes="16x16" href="favicon/favicon-16x16.png">
    <link rel="manifest" href="favicon/site.webmanifest">
    <link rel="mask-icon" href="favicon/safari-pinned-tab.svg" color="#5bbad5">
    <link rel="shortcut icon" href="favicon.ico">
    <meta name="msapplication-TileColor" content="#da532c">
    <meta name="msapplication-config" content="favicon/browserconfig.xml">
    <meta name="theme-color" content="#ffffff">
</head>

<body>
<div class="header">
<a href="https://quic.xargs.org">QUIC</a>
<a href="https://dtls.xargs.org">DTLS</a>
<a href="https://tls13.xargs.org">TLS 1.3</a>
<a href="https://tls12.xargs.org">TLS 1.2</a>
</div>
<div class="container">
<h1>Hands-on: X25519 Key Exchange</h1>
<h4>Let's exchange a secret to start a secure conversation.</h4>

<div class="section">
<h3>Overview</h3>
<p>Key exchange is a mechanism where two parties (Alice and Bob) can agree on
    the same number without an eavesdropper being able to tell what it is.
    X25519 is the name of one method of key exchange, by doing point operations
    on the Curve25519 elliptic curve:
<div class="text-center pb1">
<span class="math">y<sup>2</sup> = x<sup>3</sup> + 486662x<sup>2</sup> + x</span>
</div>

<p>With those point operations, we'll be doing a key exchange that looks like
    this:
    <div class="text-center pb1">
    <span class="math">k<sub>b</sub>&lowast;(k<sub>a</sub>&lowast;P)
    = k<sub>a</sub>&lowast;(k<sub>b</sub>&lowast;P)</span>
    </div>

<p>Let's give the above terms some better names:
<table class="mb1" style="margin-left: 2em;">
    <tr>
        <td class="text-right"><span class="math">k<sub>a</sub></span></td>
        <td>&nbsp;:&nbsp;&nbsp;</td>
        <td>Alice's secret key - a 255-bit (~32-byte) random number</td>
    </tr>
    <tr>
        <td class="text-right"><span class="math">k<sub>b</sub></span></td>
        <td>&nbsp;:&nbsp;&nbsp;</td>
        <td>Bob's secret key - a 255-bit (~32-byte) random number</td>
    </tr>
    <tr>
        <td class="text-right"><span class="math">P</span></td>
        <td>&nbsp;:&nbsp;&nbsp;</td>
        <td>a point on the curve, where <span class="math">x=9</span></td>
    </tr>
    <tr>
        <td class="text-right"><span class="math">k<sub>a</sub>&lowast;P</span></td>
        <td>&nbsp;:&nbsp;&nbsp;</td>
        <td>Alice's public key</td>
    </tr>
    <tr>
        <td class="text-right"><span class="math">k<sub>b</sub>&lowast;P</span></td>
        <td>&nbsp;:&nbsp;&nbsp;</td>
        <td>Bob's public key</td>
    </tr>
    <tr>
        <td class="text-right"><span class="math">k<sub>a</sub>&lowast;k<sub>b</sub>&lowast;P</span></td>
        <td>&nbsp;:&nbsp;&nbsp;</td>
        <td>The shared secret</td>
    </tr>
</table>
Once Alice and Bob have a shared secret, they can use it to build encryption
keys for a secure connection.
</div>

<div class="section">
<h3>Math on the curve</h3>
<p>This section can be skipped, it just gives a flavor of the math of
    elliptic curves. An in-depth animated explanation for this section can
    be found on <a href="https://curves.xargs.org">a sister page</a>.
<div class="flex-container">
<div class="meat">
<p><strong>Point operations</strong> (performed on points on the curve):
<ul>
    <li><em>Adding</em> two points on the curve gives a third point, based on
        the line between two points and its intersection with the
        curve.
    <li>Repeated additions of a point on the curve gives us <em>scalar
    multiplication</em>:
    <br>&nbsp;&nbsp;<span class="math">2P=P+P</span>
    <br>&nbsp;&nbsp;<span class="math">3P=P+P+P</span>
    <br>&nbsp;&nbsp;<span class="math">6P=P+P+P+P+P+P</span>
    <br>&nbsp;&nbsp;... etc.</li>
    <li>Adding points on the curve is <em>associative</em>: adding
        the results of point addition will give the same result
        as adding the component points individually:
        <br>&nbsp;&nbsp;<span class="math">P+P+P+P = 3P+P = 2P+2P = 4P</span>
    </li>
</ul>
</div>
<div class="diagram text-center">
<!--suppress CheckImageSize-->
<img height=250 width=260
     src="images/add-points.png"
     alt="Visual demonstration of point addition">
<br>
<small><span><strong>Point Addition: P+Q=R</strong></span></small>
</div>
</div>
<div class="flex-container">
<div class="meat">
<p><strong>Modular arithmetic</strong> (used when calculating
    addition and multiplication of points above):
<ul>
    <li>Adding, subtracting, and multiplying numbers will
        "wrap around" at the prime <span class="math">p=2<sup>255</sup>-19</span>.
    <li>Division is replaced
    with the multiplicative inverse: instead of dividing by <span class="math">x</span>
    we find the number <span class="math">x<sup>-1</sup></span>
    that satisfies the relationship <span class="math">x&lowast;x<sup>-1
    </sup>=1</span>
    in our prime field, and multiply by that.
</li>
</ul>
</div>
<div style="min-width: 20em;" class="text-center">
<div>
<strong>Examples</strong> <span class="math">(with p=23)</span>
</div>
<div>Addition: <span class="math">16+15 = 31mod23 = 8</span></div>
<div>Subtraction: <span class="math">8-13 = -5mod23 = 18</span></div>
<div>Multiplication: <span class="math">4&lowast;7 = 28mod23 = 5</span></div>
<div>Multiplicative inverse:
<span class="math">7&lowast;7<sup>-1</sup>mod23 = 1
    <br>&rarr; 7&lowast;10mod23=1; 7<sup>-1</sup> = 10</span></div>
<div>Division: <span class="math">4/7 &rarr; 4&lowast;7<sup>-1</sup>mod23
    <br>&rarr; 4&lowast;10mod23 = 17</span></div>
</div>
</div>
</div>

<div class="section">
<h3>Hands on</h3>
<p>Let's play with some actual numbers. This calculator lets us do scalar
    multiplication on the base point <span class="math">P</span>, which
    is a point on the curve with coordinate <span class="math">x=9</span>.
    These calculations only give the <span class="math">x</span>
    coordinate of <span class="math">nP</span>, the <span class="math">y</span>
    coordinate is not needed or used.</p>

<div class="calculator">
<form id="form-pubkey">
    <div class="calculator-title">
    Secret key multiplier
    </div>
    <table>
        <tr>
            <td></td>
            <td class="text-right">
                <button type="button" class="text-right" id="pubkey-plus-one">+1</button>
                <button type="button" class="text-right" id="pubkey-double">x2</button>
                <button type="button" class="text-right" id="pubkey-clamp">Clamp</button>
                <span class="help-tooltip" data-tooltip-text="Clamp: Set 5 bits
                         required by curve security, see Q&A below for full
                         explanation of clamping.">?</span>
            </td>
        </tr>
        <tr>
            <td>
            <label for="pubkey-privkey">secret key (n):</label>
            </td>
            <td>
            <input class="long right squish truncable" id="pubkey-privkey"
                   type="text" data-deco="hex-ify" value="0x1">
            </td>
        </tr>
        <tr>
            <td>
                <label for="pubkey-result">public key (nP):</label>
            </td>
            <td>
                <input class="long right squish truncable" id="pubkey-result"
                       type="text" readonly>
            </td>
        </tr>
    </table>
</form>
</div>

<p>Let's perform a simple key exchange. Give Alice a secret
    key, such as "7", and use the calculator above to find Alice's
    public key. Give Bob a different secret key, such as "5",
    and use the calculator to find Bob's public key:
<ul>
    <li>Alice's secret key: <span class="math">k<sub>a</sub></span>
        = <span class="squish">7</span>
    <li>Alice's public key: <span class="math">k<sub>a</sub>P</span>
    <span class="math">(7P)</span> =
    <span class="squish truncable">0daf32e7ed8099122b2dfa4c1d8c4a20c0972a1538bf0575338aae0fe0841828</span>
    <li>Bob's secret key: <span class="math">k<sub>b</sub></span>
        = <span class="squish">5</span>
    <li>Bob's public key: <span class="math">k<sub>b</sub>P</span>
    <span class="math">(5P)</span> =
    <span class="squish truncable">41b6ec3c50ee7af203c0026e5e079e7fa8cbc9bc581d49cb0d537d5778497c87</span>
</ul>

<p>Now let's be Alice. Put Alice's secret key
    (<span class="math">k<sub>a</sub></span>) into the calculator below,
    and use it to multiply Bob's public key
    (<span class="math">k<sub>b</sub>P</span>).
<ul>
    <li>Shared secret: <span class="math">k<sub>a</sub>k<sub>b</sub>P</span>
    <span class="math">(35P)</span> =
    <span class="squish truncable">1b9b715c415e547a13ca98a9f561d54499cc7402a1098414eddcfaf83ffbe3f8</span>
    </li>
</ul>

<div class="calculator">
<form id="form-mult">
    <div class="calculator-title pb1">
    Public key multiplier
    </div>
    <table>
        <tr>
            <td>
                <label for="mult-n">secret key (n):</label>
            </td>
            <td>
                <input class="long text-right squish truncable" id="mult-n"
                       type="text" data-deco="hex-ify" placeholder="multiplier">
            </td>
        </tr>
        <tr>
            <td>
                <label for="mult-point">public key (Q):</label>
            </td>
            <td>
                <input class="long text-right squish truncable" id="mult-point"
                       type="text" data-deco="hex-ify" placeholder="point">
            </td>
        </tr>
        <tr>
            <td>
                <label for="mult-result">new point (nQ):</label>
            </td>
            <td>
                <input class="long text-right squish truncable" id="mult-result"
                       type="text" placeholder="result" readonly>
            </td>
        </tr>
    </table>
</form>
</div>

<p>Let's switch over to Bob. Put Bob's secret key
    (<span class="math">k<sub>b</sub></span>) into the calculator, and
    use it to multiply Alice's public key
    (<span class="math">k<sub>a</sub>P</span>).
    The result matches, because
    <span class="math">k<sub>a</sub>k<sub>b</sub>P = k<sub>b</sub>k<sub>a</sub>P = 35P</span>.
</p>

<p>Since the eavesdropper can't see either of Alice or Bob's secret keys,
    they can't compute the same result.
</p>
</div>

<div class="section">
<h3>Odds and ends</h3>
<p><span class="qa">Q:</span> Why can't I reproduce
    these results in <xtt>openssl</xtt> or other tools?

<p><span class="qa">A:</span> Private keys used in actual Curve25519
    are modified slightly to avoid particular attacks
    (see section 4.7 "Clamping" in <a
            href="https://martin.kleppmann.com/papers/curve25519.pdf"
    >Implementing Curve25519/X25519</a> by Martin Kleppmann).
    In particular the following five bits are clamped to
    pre-determined values in real implementations (click the "Clamp" button
    to apply these bit values to your secret key):
<table class="table table-condensed table-not-full" style="margin-left: 2em;">
    <thead>
    <tr><th>Bits</th><th>Value</th><th>Reason</th></tr>
    </thead>
    <tr><td>0,1,2</td><td>0</td><td>Protect against small-subgroup attacks</td></tr>
    <tr><td>254</td><td>1</td><td>Prevent a timing leak</td></tr>
    <tr><td>255</td><td>0</td><td>Constrain n < 2<sup>255</sup></td></tr>
</table>

<p>You may still find that your output does not match
    because X25519 keys are stored and transmitted in little-endian
    order while this page displays them as plain numbers. Flipping the byte
    order should match them up.</p>

<p><span class="qa">Q:</span> If these are points in
    an x-y curve, where are the y coordinates?

<p><span class="qa">A:</span>
    The <span class="math">y</span> coordinates for each point are not needed
    for X25519, and for simplicity they are not computed.
    Using only the <span class="math">x</span> coordinate also reduces
    public key length, as the <span class="math">y</span> coordinate isn't part of
    the key.

<p>Each valid point on the curve has two
    <span class="math">y</span> values that satisfy
    <span class="math">sqrt(y<sup>2</sup>)</span>.

<div class="calculator">
<form id="form-xy">
    <div class="calculator-title pb1">
    Y-coordinate calculator
    </div>
    <table>
        <tr>
            <td>
                <label for="xy-x">x:</label>
            </td>
            <td>
                <input class="long text-right squish truncable" id="xy-x"
                       type="text" data-deco="hex-ify" value="0x0">
            </td>
        </tr>
        <tr>
            <td>
                <label for="xy-y1">y<sub>1</sub>:</label>
            </td>
            <td>
                <input class="long text-right squish truncable" id="xy-y1"
                       type="text" value="0x0" readonly>
            </td>
        </tr>
        <tr>
            <td>
                <label for="xy-y2">y<sub>2</sub>:</label>
            </td>
            <td>
                <input class="long text-right squish truncable" id="xy-y2"
                       type="text" value="0x0" readonly>
            </td>
        </tr>
    </table>
</form>
</div>

<p>Only half of <span class="math">x</span> values are valid on Curve25519.
    Going back to our curve equation, valid means that the expression
    <span class="math">x<sup>3</sup> + 486662x<sup>2</sup> + x</span>
    results in a number that in modular arithmetic has a square root
    (to satisfy the
    <span class="math">y<sup>2</sup></span> side of the equation).

<p><span class="qa">Q:</span> What does Curve25519 look like?</p>

<p><span class="qa">A:</span> Here's what the curve looks like in real numbers,
    (i.e. floating point numbers with standard addition and multiplication):
<img class="cute-graph center-block"
     src="images/curve25519-real.png"
     alt="an elliptic curve">
<div class="text-center">
<p><span class="math">y<sup>2</sup> = x<sup>3</sup> + 486662x<sup>2</sup> +
    x</span>
</div>

<p>And here's the first points of the curve when calculated in
    𝔽<sub>p</sub> (i.e. with integers 0..2<sup>255</sup>-19 using
    modular math):</p>
<img class="cute-graph center-block"
     src="images/curve25519-field.png"
     alt="a pattern of dots, mirrored horizontally, but otherwise seemingly without pattern">
<div class="text-center">
<p><span class="math">y<sup>2</sup> = x<sup>3</sup> + 486662x<sup>2</sup> +
    x</span> in 𝔽<sub>p</sub>
</div>

<p><span class="qa">Q:</span> Can you give me more
details on elliptic curve operations?

<p><span class="qa">A:</span> I found the following
useful:
<ul>
    <li><a href="https://cr.yp.to/ecdh/curve25519-20060209.pdf"
    >Curve25519: new Diffie-Hellman speed records</a> - explains the curve and how it was derived</li>
    <li><a href="https://curves.xargs.org">The Animated Elliptic Curve</a>
        - an animated exploration of the concepts behind EC cryptography</li>
    <li><a href="https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication"
    >Wikipedia: EC point multiplication</a> - particularly the section on
        Montgomery ladders
    </li>
    <li><a href="https://en.wikipedia.org/wiki/Montgomery_curve#Montgomery_arithmetic"
    >Wikipedia: Montgomery arithmetic</a> - includes equations for addition and
        doubling of points</li>
    <li><a href="https://datatracker.ietf.org/doc/html/rfc7748">RFC 7748</a>
    - recommended algorithm for X25519 multiplication in
    constant time with a Montgomery ladder</li>
    <li><a href="https://martin.kleppmann.com/papers/curve25519.pdf"
    >PDF: Implementing Curve25519/X25519</a> - as noted above</li>
    <li><a href="https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/"
    >Elliptic Curve Cryptography: a gentle introduction</a></li>
</ul>
</div>

<div class="outerblock">
<p>The code for this project can be found
    <a href="https://github.com/syncsynchalt/illustrated-x25519">on GitHub</a>.</p>
</div>

<div class="outerblock">
<p>If you found this page useful or interesting let me know via Twitter
    <a href="https://twitter.com/xargsnotbombs">@XargsNotBombs</a>.</p>
</div>
</div>
</body>
</html>
